\documentclass[12pt, a4paper]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{color}
\usepackage{url}
\definecolor{lnk}{rgb}{0,0,0.4}
\usepackage[colorlinks=true,linkcolor=lnk,citecolor=black,urlcolor=black]{hyperref}
\usepackage{./otros/caratula}
\usepackage{amssymb}			
\usepackage{pdfpages}
\usepackage{makeidx}

%\usepackage{moreverb}
\usepackage{fancyvrb}

\parskip=1.5pt
	
\usepackage[small, bf, labelformat = empty]{caption}	
\usepackage{subfig}
\usepackage{float}
\restylefloat{table}

\makeindex
	
\begin{document}

%~ Carátula
	%\titulo{Trabajo Pr\'actico - Jay Formatter}
	\titulo{Trabajo Pr\'actico: Jay Formatter}
	%\subtitulo{Grupo: Sir Lambda y su Orquesta Fuertemente Tipada}
	\fecha{11 de Julio de 2012. \\}
	\materia{Teor\'ia de Lenguajes}
	\integrante{Heredia Nadia}{589/08}{nheredia@dc.uba.com}	    
	\integrante{Paz, Daniel}{407/08}{dpaz@dc.uba.ar}	
    \integrante{Varaschin, Nicolás}{187/08}{nvaraschin@dc.uba.ar}
	\maketitle

% Índice
\small
\newpage \printindex \tableofcontents
\normalsize
\newpage


\newcommand{\nom}[1]{\ensuremath{\mathsf{#1}}}

\section{Gram\'atica de Jay}

\subsection{Tokens}
\begin{Verbatim}
reserved    ::= 'boolean', 'else', 'if', 'int', 'main', 
                'void', 'while', 'true', 'false'
LITERAL     ::= un número o un booleano "[0-9]+|true|false"

Separators
LPAREN      ::= (
RPAREN      ::= )
LBRACE      ::= {
RBRACE      ::= }
COMMA       ::= ,
SEMICOLON   ::= ;

Operators
EQUALS      ::= =
ADD         ::= +
SUB         ::= -
MUL         ::= *
DIV         ::= /
LOWER       ::= <
LEQ         ::= <=
BIGGER      ::= >
BEQ         ::= >=
EQUAL       ::= ==
NEQ         ::= !=
AND         ::= &&
OR          ::= ||
NOT         ::= !

IDENTIFIER  ::= nombre de variable "[a-zA-Z][a-zA-Z0-9]*"

Además 
ignore      ::= ignorar los espacios "\t\r\f"
COMMENT     ::= ignorar los comentarios "//.*"
newline     ::= salto de línea "\n+"
\end{Verbatim}

Notar que fue necesario distinguir cada separador y operador, de lo
contrario se dificultar\'ia mucho el escribir las producciones de 
la gram\'atica. 
Si se esperaba un par\'entesis que abre, lo mejor es tener un 
token para esto y no engoblarlo dentro de uno que sea separador 
y despu\'es preguntar si es efectivamente lo buscado.

%modo de uso: python jay_parser.py < archivo_entrada > archivo_salida
%ejemplo: python jay_parser.py < /ejemplos/p4.jay > /ejemplos/p4.html

\subsection{Producciones}
\begin{Verbatim}[commentchar=\%, fontfamily=tt]
program         ::= VOID MAIN LPAREN RPAREN LBRACE prog

prog            ::= RBRACE 
                  | declarations RBRACE
                  | statements RBRACE
                  | declarations statements RBRACE

declarations    ::= declaration 
                  | declaration declarations
                  
statements      ::= statement 
                  | statement statements

declaration     ::= type identifiers SEMICOLON

type            ::= INT 
                  | BOOLEAN

identifiers     ::= IDENTIFIER 
                  | IDENTIFIER COMMA identifiers

statement       ::= SEMICOLON
                  | block 
                  | assignment 
                  | ifStatement 
                  | whileStatement
                  
block           ::= LBRACE RBRACE 
                  | LBRACE statements RBRACE

assignments     ::= IDENTIFIER EQUALS expression SEMICOLON

ifStatement     ::= IF LPAREN expression RPAREN statement
                  | IF LPAREN expression RPAREN statement ELSE statement
                  
whileStatement  ::= WHILE LPAREN expression RPAREN statement

expression      ::= conjunction 
                  | conjunction OR expression

conjunction     ::= relation 
                  | relation AND conjunction

relation        ::= addition 
                  | addition LOWER relation
                  | addition LEQ relation
                  | addition BIGGER relation 
                  | addition BEQ relation 
                  | addition EQUAL relation 
                  | addition NEQ relation

addition        ::= term 
                  | term ADD addition
                  | term SUB addition

term            ::= negation
                  | negation MUL term
                  | negation DIV term
                  
negation        ::= factor 
                  | NOT factor

factor          ::= IDENTIFIER 
                  | LITERAL 
                  | LPAREN expression RPAREN
\end{Verbatim}

\noindent
Se realizaron las siguientes modificaciones a las producciones
\begin{enumerate}
    \item eliminaci\'on de para eliminar producciones lambda 
    \item eliminaci\'on de recursi\'on a izquierda
\end{enumerate}

\section{Formateo usando HTML}
\noindent
Para la traducci\'on de una cadena de \textsl{Jay} a una 
correspondiente de \textsl{HTML} se utiliz\'o traducci\'on 
dirigida por la sint\'axis. 
Para los atributos visuales se us\'o la siguiente 
stylesheet

\VerbatimInput[fontsize=\small]{ejemplos/jay.css}

\subsection{Atributos}
\noindent
Los no terminales contienen los siguientes atributos

\begin{itemize}
    \item \textbf{code} cadena del lenguaje HTML asociada 
            al c\'odigo que la contiene.
    \item \textbf{ids} lista de tuplas cuyas segundas 
            componentes son los identificadores definidos y 
            utilizados. La primera componente de cada tupla 
            indica si se trata de una definici\'on (Def), o de 
            un uso (Use). Esta lista se usa para verificar que 
            los identificadores de variable hayan sido definidos 
            antes de ser usados. Como los ids se van guardando a 
            medida que aparecen en el c\'odigo, si se encuentra 
            un uso antes que una definici\'on se considera un
            error.
\end{itemize}

\noindent
Se tuvo en cuenta que todos los tokens tienen un valor ya 
definido que se corresponde consigo mismo. 
Por ejemplo, el valor del token \texttt{WHILE} dentro del código 
es “while”. 
Además, los tokens y no terminales poseen un valor de tipo string.
Esto significa que no hace falta acceder a un atributo de la forma
s\'imbolo.valor, sino que el s\'imbolo (como variable) ya es 
justamente la cadena buscada.
De esta forma, se pudieron ir sintetizando los c\'odigos 
correspondientes. 

\subsection{Implementaci\'on}
\noindent
Se utiliz\'o la biblioteca \texttt{PLY} de Python, que 
implementa el lexer lex y el parser yacc (que es LALR). 
Se le indic\'o al lexer los tokens a reconocer, luego al 
parser la gr\'amatica que se quiere identificar, y por \'ultimo;
lo m\'as importante; el c\'odigo a ejecutar al aplicar cada 
producci\'on.\\

\noindent
La forma de definir el c\'odigo a ejecutar es la siguiente:

\begin{Verbatim}
p_nombre_produccion(self, p):
    """ produccion usando BNF """
    codigo
\end{Verbatim}
\noindent donde \textbf{p} es una lista conteniendo los 
s\'imbolos que est\'an involucrados en la producci\'on 
especificada. \\
Por ejemplo si la producci\'on es 
\texttt{E : E '+' F}, entonces p ser\'a 
\texttt{[E, E, '+', F]}.

\section{Expresiones v\'alidas de Jay}
\noindent
Los siguientes son ejemplos de formatting de c\'odigo v\'alido 
de Jay. El c\'odigo HTML producido no se incluye en el informe 
pero puede encontrarse dentro de la carpeta src/ejemplos.

\paragraph{p1}
\noindent \textbf{Input}
\VerbatimInput[fontsize=\small]{ejemplos/p1.jay}
\noindent \textbf{C\'odigo formateado}
\begin{figure}[H]
    \includegraphics[scale=0.6]{ejemplos/p1.png}
\end{figure}

\paragraph{p3}
\noindent \textbf{Input}
\VerbatimInput[fontsize=\small]{ejemplos/p3.jay}
\newpage
\noindent \textbf{C\'odigo formateado}
\begin{figure}[H]
    \includegraphics[scale=0.6]{ejemplos/p3.png}
\end{figure}

\paragraph{p5}
\noindent \textbf{Input}
\VerbatimInput[fontsize=\small]{ejemplos/p5.jay}
\noindent \textbf{C\'odigo formateado}
\begin{figure}[H]
    \includegraphics[scale=0.6]{ejemplos/p5.png}
\end{figure}

\newpage
\section{Expresiones inv\'alidas de Jay}

\subsection{Tipos de errores}

\paragraph{Caracter no v\'alido}
Este error ocurre cuando el lexer no puede reconocer el tipo de 
token que est\'a leyendo, porque no matchea con ninguno de los 
que est\'an definidos. 

\paragraph{Identificador no definido}
Como se mencion\'o en la parte de atributos de los no  
terminales, se mantiene una lista con los identificadores, que 
se utiliza para saber si los usos de los identificadores ocurren 
despu\'es de sus respectivas definiciones. 
La posici\'on en el c\'odigo de este error es la del primer 
identificador no definido.

\paragraph{Sint\'axis inv\'alida y sentencia incompleta}
Los errores restantes, son aquellos provistos por yacc, que 
tienen que ver con la posibilidad de reducir expresiones en otras, es decir, de apilcar producciones para hacer reducciones.
Existen dos tipos de errores
\begin{enumerate}
    \item  \textbf{sint\'axis inv\'alida} 
            cuando un token invalida las producciones aplicables 
            a futuro.
    \item  \textbf{sentencia incompleta}
            cuando no hay m\'as tokens disponibles y no existe 
            una producci\'on para reducir la \'ultima parte de 
            la cadena.
\end{enumerate}

\subsection{Mostrando los errores}
\noindent
Para que las emisiones de errores tengan un formato consistente, 
se decidi\'o modularizar el c\'odigo, teniendo una funci\'on 
especial encargada de manejar los errores. 
Al mostrar el error, se ven varias l\'ineas, no s\'olo la que 
contiene el error, con esto se intenta dar contexto para 
facilitar la comprensi\'on. La l\'inea en la que se encuentra
el error se precede con el s\'imbolo \texttt{>}.

\subsection{Ejemplos}
%\noindent
%Se muestra el output de stderr.

\paragraph{p2}
\noindent \textbf{Input}
\VerbatimInput[fontsize=\small]{ejemplos/p2.jay}
\noindent \textbf{Output}
\VerbatimInput[fontsize=\small]{ejemplos/p2.out}

\paragraph{p4}
\noindent \textbf{Input}
\VerbatimInput[fontsize=\small]{ejemplos/p4.jay}
\noindent \textbf{Output}
\VerbatimInput[fontsize=\small]{ejemplos/p4.out}

%\paragraph{p5}
%\noindent \textbf{Input}
%\VerbatimInput[fontsize=\small]{ejemplos/p5.jay}
%\noindent \textbf{Output}
%\VerbatimInput[fontsize=\small]{ejemplos/p5.out}



\section{Ejecutando el formatter}
\noindent
Para ejecutar el programa y mostrar el c\'odigo HTML resultante 
por pantalla, debe ejecutarse lo siguiente: \\
\texttt{python main.py <} \texttt{input.jay} \\

\noindent
Para generar un archivo de salida HTML, debe ejecutarse:
\\
\texttt{python main.py <} \texttt{input.jay >} 
\texttt{output.html}

\section{C\'odigo del formatter}

\VerbatimInput[fontsize=\small]{../src/main.py}

\end{document}

